4361. Solarium for mushrooms (Hard)

And again Michael does his experiments. This time he decided to clone the mushrooms. For this, he prepared n spores, which soon will plant in the ground and grow. When spores will develop and increase in size, they haven't touch each other, so Michael decided to plant them only at integer coordinates. And also to speed up the growth process, he is going to build a large round lamp to warm them. The center of the lamp he wants to place at point with integer coordinates, and let the radius of the lamp be integer too. But how to define it? Of course, you can build a lamp under which the whole forest can be hidden, but it will take a lot of extra time. So, the radius of the lamp must be as small as possible.

Input. The number of spores n (0 ≤ n ≤ 3141592649625).

Output. Print the smallest integer radius of the lamp, under which all the n spores can hide.

Sample input	Sample output
5	1

SOLUTION

binary search

Algorithm analysis

Divide the set of points with integer coordinates into five parts as shown in the figure: one point lies in the center, the other four sets are equal to each other and cover four parts of the circle. If the number of points in the first quarter is res, then the total number of points in the circle is 4 * res + 1.

Let’s find the value of res. Radius of a circle equals to r. Iterate values of y from 0 to r. Then the axis y = k (0 ≤ k ≤ r) inside the circle contains exactly integer points. Therefore, the total number of points res in the first quarter is

Let f(r) be the number of points in a circle of radius r. Then

f(r) = 4 * + 1

Function f is increasing. In the problem, you need to find the minimum r for which f(r) = n. Search the lamp radius r using a binary search.

Algorithm realization

Function count returns the number of points with integer coordinates in a circle of radius r.

long long count(long long r)

{

long long res = 0;

double r2 = r*r;

for(long long y = 0; y <= r; y++)

res += (long long)sqrt(r2 - y*y);

return 4 * res + 1;

}

The main part of the program. Read the input value n.

scanf("%lld",&n);

The radius of a circle that covers at least n points can be found with a binary search. Initially we assume that radius is in the interval [l; r] = [0; 1000000].

l = 0; r = 1000000;

while(l < r)

{

m = (l + r ) / 2;

If the number of points in a circle of radius m is less than n, then we increase the left boundary of the interval to m + 1 (radius m is not enough to cover n points). Otherwise, we reduce the right boundary.

if (count (m) < n) l = m + 1; else r = m;

}

Print the answer.

printf("%d\n",l);